1. Field of the Invention
The present invention relates to an arithmetic operation method for a cyclic redundancy check (CRC) and an arithmetic operation circuit for the CRC and more particularly to the arithmetic operation method for the CRC and the arithmetic operation circuit for the CRC being suitably usable when data communications are performed through different communications protocols.
The present application claims priority of Japanese Patent Application No.2001-059807 filed on Mar. 5, 2001, which is hereby incorporated by reference.
2. Description of the Related Art
FIG. 15 is a schematic block diagram showing an example of configurations of a conventional data communications system. As shown in FIG. 15, the conventional data communications system of the example is so configured that an information processing system 1 such as a personal computer or a like is connected through a network 4 such as an intranet, internet, or a like to a server 2 provided with a hard disc 3. As a communications protocol for data communications carried out between the information processing system 1 and the server 2, generally, a TCP/IP (Transmission Control Protocol/Internet Protocol) (hereinafter called a “general protocol”) is used. As a communications protocol for data communications carried out between the server 2 and the hard disc 3, a new high-speed communications protocol (hereinafter called a “high-speed protocol”) such as “InfiniBand” (Trade name) which is a next-generation interface for a server and can provide a data transmission speed of not less than 500 M byte/second is used.
Next, operations of the data communications system having the configurations described as above are explained in which access is made from the information processing system 1 to the server 2 through the network 4 and data stored in the hard disc 3 is read. First, the server 2, when receiving an access made from the information processing system 1 and a request for reading data stored in the hard disc 3, searches for a memory location in the hard disc 3 to acquire requested data. The hard disc 3 then reads the requested data and transmits read data to the server 2 through a cable 5. At this point, the data is incorporated into communications data configured in a data format shown in FIG. 16 and is transmitted 4 bytes by 4 bytes (32 bits) from the hard disc 3 to the server 2 in accordance with the high-speed protocol. As shown in FIG. 16, the communications data is made up of a header, data, and arithmetic operation results CRC32 and CRC16. The arithmetic operation result CRC32 represents a result obtained by an arithmetic operation for error detection by dividing the data to be transmitted into strings of data each being made up of 32 bits and by using a 32nd order generative polynomial expressed by a following equation (1) in accordance with CRC method which is one of error detection methods usable in data communications. Similarly, the arithmetic operation result CRC16 represents a result obtained by an arithmetic operation for error detection by dividing the data to be transmitted into strings of data each being of 16 bits and by using a 16th order generative polynomial shown in a following equation (2) in accordance with the CRC method. Hereinafter, the arithmetic operation for error detection using the 32nd order generative polynomial shown in the equation (1) is referred to as a “CRC32 operation” and the arithmetic operation for error detection using the 16th order generative polynomial shown in the equation (2) is referred to as a “CRC16 operation”.G(X)=X32+X26+X23+X22+X16+X12+X11+X8+X7+X5+X4+X2+X1+1  Equation (1)G(X)=X16+X12+X3+X1+1  Equation (2)
As shown in FIG. 17, the header and the data contained in the communications data are divided into “n” (n is a natural number) pieces of data blocks DB0 to DBn−1 each being made up of one byte. The arithmetic operation result CRC32 contained in the communications data is divided into four pieces of arithmetic operation result blocks CRC320 to CRC323 each being made up of one byte. The arithmetic operation result CRC16 contained in the communications data is divided into two pieces of arithmetic operation result blocks CRC160 to CRC161. The CRC32 operation is performed on the header and the data contained in the communications data. On the other hand, the CRC16 operation is performed on the header, data, and arithmetic operation result CRC32. That is, in the CRC16 operation, the arithmetic operation result CRC32 is treated the same as header and data contained in the communications data.
Next, the server 2, when having received the communications data from the hard disc 3, transmits new communications data obtained by removing a header prepared specifically for a high-speed protocol and the arithmetic operation result CRC16 from the received communications data to the information processing system 1 through the network 4.
As described above, in the conventional communications system, when the communications data is transmitted from the hard disc 3 to the server 2, the CRC 32 operation is performed to add the arithmetic operation blocks CRC320 to CRC323 to the communications data. Therefore, the CRC operation is not required when the communications data is transmitted from the server 2 to the information processing system 1, thus enabling communications data to be transmitted in a short time.
Next, configurations and operations of a conventional CRC arithmetic operation circuit are described which perform CRC operations when communications data is transmitted from the hard disc 3 to the server 2. FIG. 18 is a block diagram showing configurations of the conventional CRC arithmetic operation circuit. The conventional CRC arithmetic operation circuit includes a data inputting section 11, latches 12 to 16, selectors 17 and 18, arithmetic operation sections 19 and 20, and a data outputting section 21.
The data inputting section 11 is an interface to perform waveform shaping on input data D0 being input 32 bits by 32 bits which is read from a specified memory area in the hard disc 3 and to input it as output data D1 to circuit elements at a later stage. Each of the latches 12 and 13 is made up of a 32-bit flip-flop FF which is used to adjust timing for data processing. The latch 12 latches the output data D1 from the data inputting section 11 for a period of time being equivalent to one clock fed from an outside and then outputs it as output data D2. The latch 13 latches the output data D2 from the latch 12 for a period of time being equivalent to one clock and outputs it as output data D4. The latch 14 is made up of a 32-bit flip-flop FF and, in order to adjust timing with which data is input to the arithmetic operation section 20, latches the output data D1 fed from the data inputting section 11 for a period of time being equivalent to one clock and outputs it as output data D2.
The selector 17 selects either of the output data D2 being output by 32 bits from the latch 14 or output data D5 being output by 32 bits from the latch 15 and outputs it as output data D3.
The arithmetic operation section 19 performs the CRC32 operation on the output data D1 from the data inputting section 11 by using the output data D5 from the latch 15. The arithmetic operation 20 performs the CRC16 operation on the output data D3 by using output data D6 from the latch 16. The latch 15 is made up of a 32-bit flip-flop FF and latches an arithmetic operation result of 32 bits output from the arithmetic operation section 19 for a period of time being equivalent to one clock and outputs it as the output data D5. The latch 16 is made up of a 16-bit flip-flop FF and latches an arithmetic operation result of 16 bits output from the arithmetic operation section 20 for a period of time being equivalent to one clock and outputs it as output data D6. The selector 18 selects any one of the output data D4 being output by 32 bits from the latch 13, output data D5 being output by 32 bits from the latch 15 and output data D6 being output by 16 bits from the latch 16 and outputs it as output data D7. The data outputting section 21 is an interface to perform waveform shaping on output data D7 being output by 32 bits from the selector 18 and to feed it as output data D8 to circuit elements at a later stage.
Next, configurations of the conventional arithmetic operation sections 19 and 20 will be described in detail.
The arithmetic operation section 19 produces an arithmetic operation result CRC32. A polynomial P(X) used to obtain the arithmetic operation result CRC32 is given below, in which a bit string having 32 bits “d31, d30, . . . , d1, d0” is considered to be a value.P(X)=d31X31+d30X30+ . . . +d1X+d0  Equation (3)In the above equation, the symbol “+” indicates that calculations are done by a “modulo-two addition” operation in the polynomial. The symbol “+” in the equations (1) and (2) and in the equations shown hereinafter has the same meaning as described above. The “modulo-two operation” refers to an operation in which calculations are done cyclically using only a binary number “0” or “1” without carrying over or rounding off a place and is defined by following equations (4) to (11).0+0=0  Equation (4)0+1=1  Equation (5)1+0=1  Equation (6)1+1=0  Equation (7)0−0=0  Equation (8)0−1=1  Equation (9)1−0=1  Equation (10)1−1=0  Equation (11)
That is, results from the “modulo-two operation” turn out to be the same as those obtained from an exclusive OR (EOR) operation in a logic circuit.
A result obtained by multiplying the input data P (X) by the highest order term X32 included in the 32nd order generative polynomial G (X) shown in the equation (1) is represented by Q (X) shown in an equation (12). Then, the Q (X) is divided by the generative polynomial G (X) and its remainder is represented by R (X) shown in an equation (13). In the equation (13), each of c31, c30, . . . , c1, and c0 is “0” or “1”.Q(X)=d31X63+d30X62+ . . . +d1X33+d0X32  Equation (12)R(X)=c31X31+c30X30+ . . . +c1X+c0  Equation (13)
Each of the “c31, c30, . . . , c1, c0” constituting the remainder R (X) is a cyclic check bit of the arithmetic operation result CRC32, which is called a “CRC code”. Moreover, a new Q (X) is produced by multiplying input data P′ (X) to be input next by a CRC code obtained this time. By dividing the new Q (X) by the generative polynomial G (X), a new CRC code is obtained. When the processing described above is performed repeatedly (in a cyclic manner) on all the input data P (X), the arithmetic operation result CRC32 can be obtained.
As described above, in the CRC32 arithmetic operation, it is necessary to divide the Q (X) by the generative polynomial G (X). However, this division cannot be done simply by hardware because the hardware cannot perform high-speed processing or because large-sized circuits have to be used as the hardware and, therefore, the division is generally done using such the arithmetic operation section 19 as shown in FIG. 19. The arithmetic operation section 19 is made up of exclusive OR (EOR) gates 231 to 2314 and delay flip-flops FF 241 to FF 2432. This configuration is well known and; therefore its description is omitted accordingly. The output data C31 to C00 each being output from each of the delay flip-flops FF 2432 to FF 241 when a clock used to shift 32 bits of data whose number of its bits is equal to that of the 32-bit input data P (X) is fed to the arithmetic operation section 19 shown in FIG. 19 represents the remainder “c31, c30, . . . , c1, c0” of the CRC32 operation. FIGS. 20 and 21 show operational expressions for output data C31 to C00. In FIGS. 20 and 21, each of R31 to R00 is an initial value of each of the delay flip-flops FF 2432 to FF 241 and each of D31 to D00 corresponds to each of the bit strings d31, d30, . . . , d1, d0 making up the input data P (X) and the symbol “□” denotes an exclusive OR operation.
FIG. 22 is a block diagram showing configurations of the arithmetic operation section 20 in the conventional CRC arithmetic operation circuit. The conventional arithmetic operation section 20 is made up of exclusive OR (EOR) gates 261 to 264 and delay flip-flops FF 271 to FF 2716. This configuration is well known and; therefore its description is omitted accordingly. The arithmetic operation section 20 produces an arithmetic operation result CRC16. The CRC16 operations are approximately the same as the CRC32 operation except that polynomials to be used are different from each other and their descriptions are omitted accordingly.
The output data C15 to C00 each being output from each of the FFs 2716 to 271 when a clock to used shift 32 bits of data whose number of its bits is equal to that of the 32-bit input data P (X) is fed to the arithmetic operation section 20 shown in FIG. 23 represents the remainder of the CRC16 operation. FIG. 23 shows an operational expression for output data C15 to C00. In FIG. 23, each of R15 to R00 is an initial value of the FF2716 to FF271 and each of the D31 to D00 corresponds to each of the strings of bits d31, d30, . . . , d1, d0 making up the input data P (X) and the symbol “□” denotes the exclusive OR operation.
Next, operations of the conventional CRC arithmetic operation circuit are described by referring to a timing chart shown in FIG. 24. To simplify the description, let it be assumed that input data D0 is made up of byte data BD0 to BD3 as shown in FIG. 24. The byte data BD0 is made up of data blocks DB0 to DB3 each being of one byte and the byte data BD1 is made up of data blocks DB4 to DB7 each being of one byte. The byte data BD2 is made up of data blocks DB8 to DB11. The byte data BD3 is made up of data blocks DB12 and DB13 each being of one byte.
First, as shown in FIG. 24(1), when the input data D0 is sequentially fed from an outside to the CRC arithmetic operation circuit in synchronization with a clock (not shown), the data inputting section 11 performs waveform shaping on the input data D0 starting from a first period #1 and feeds it as the output data D1 to the latches 12 and 14 and to the arithmetic operation section 19 sequentially. Each of the latches 12 and 14 latches the output data D1 fed from the data inputting section 11 for a period of time being equivalent to one clock fed from the outside and then outputs the latched data D1 as the output date D2 sequentially, starting from a second period #2.
On the other hand, the arithmetic operation section 19, during the first period #1, performs the CRC32 operation on the output data D1, that is, on the byte data BD0 in the example shown in FIG. 24 by using an output data D5 output from the latch 15, that is, the initial value of the latch 15 in the example and produces an arithmetic operation result CR00. In the latch 15, “0” is set in advance as its initial value. Then, the latch 15 latches the arithmetic operation result CR00 output from the arithmetic operation section 19 for a period of time being equivalent to one clock and, as shown in FIG. 24(2), outputs it as the output data D5 during the second period #2. Next, the arithmetic operation section 19, during the second period #2, performs the CRC32 operation on the output data D1 from the data inputting section 11, that is, on the byte data BD1 in the example shown in FIG. 24, by using the output data D5 from the latch 15, that is, the arithmetic operation result CR00 in the example and produces an arithmetic operation result CR01. Then, the latch 15 latches the arithmetic operation result CR01 for a period of time being equivalent to one clock and, as shown in FIG. 24(2), outputs it as the output data D5 during a third period #3.
Similarly, the arithmetic operation section 19, during the third period #3, performs the CRC32 operation on the output data D1 from the data inputting section 11, that is, on the byte data BD2 in the example by using the output data D5 from the latch 15, that is, the arithmetic operation result CR01 in the example and produces an arithmetic operation result CR02. Then, the latch 15 latches the arithmetic operation result CR02 for a period of time being equivalent to one clock and, as shown in FIG. 24(2), outputs it as the output data D5 during a fourth period #4. Next, the arithmetic operation section 19, during the fourth period #4, performs the CRC32 operation on the output data D1 from the data inputting section 11, that is, on the byte data BD3 in the example, by using the output data D5 from the latch 15, that is, the arithmetic operation result CR02 in the example and produces an arithmetic operation result CR03. Then, the latch 15 latches the arithmetic operation result CR03 for a period of time being equivalent to one clock and, as shown in FIG. 24(2), outputs it as the output data D5 during a fifth period #5. This arithmetic operation result CR03 becomes the arithmetic operation result CRC32. Thus, the arithmetic operation result CRC32 is made up of 4 pieces of arithmetic operation result blocks CRC320 to CRC323.
The selector 17, as shown in FIG. 24(4), during the second period #2 to the fourth period #4, selects the output data D2 output from the latch 14, that is, any one of the byte data BD0 to BD2 in the example and outputs it as the output data D3. Moreover, the selector 17, as shown in FIG. 24(4), during the fifth period #5, produces new byte data BD′3 using data blocks DB12 and DB13 making up the byte data BD3 and arithmetic operation blocks CRC320 and CRC321 making up the arithmetic operation result CRC32 and outputs it as the output data D3. Furthermore, the selector 17, as shown in FIG. 24(4), produces new byte data BD4 using arithmetic operation blocks CRC322 during the sixth period#6 and CRC323 making up the arithmetic operation result CRC32 and outputs it as the output data D3.
Therefore, the arithmetic operation section 20, during the second period #2, performs the CRC16 operation on the output data D3 from the selector 17, that is, on the byte data BD0 in the example, by using output data D6 from the latch 16, that is, the initial value of the latch 16 in the example and produces an arithmetic operation result CR10. In the latch 16, “0” is set in advance as its initial value. Then, the latch 16 latches the arithmetic operation result CR10 output from the arithmetic operation section 20 for a period of time being equivalent to one clock and, as shown in FIG. 24(5), outputs it as the output data D6 during the third period #3. Next, the arithmetic operation section 20, during the third period #3, performs the CRC16 operation on the output data D3 from the selector 17, that is, on the byte data BD1 in the example, by using output data D6 from the latch 16, that is, the arithmetic operation result CR10 in the example and produces an arithmetic operation result CR11. Then, the latch 16 latches the arithmetic operation result CR11 for a period of time being equivalent to one clock and, as shown in FIG. 24(5), outputs it as the output data D6 during the fourth period #4.
Similarly, the arithmetic operation section 20, during the fourth period #4, performs the CRC16 operation on the output data D3 from the selector 17, that is, on the byte data BD2 in the example, by using output data D6 from the latch 16, that is, the arithmetic operation result CR11 in the example and produces an arithmetic operation result CR12. Then, the latch 16 latches the arithmetic operation result CR12 for a period of time being equivalent to one clock and, as shown in FIG. 24(5), outputs it as the output data D6 during the fifth period #5. Next, the arithmetic operation section 20, during the fifth period #5, performs the CRC16 operation on the output data D3 from the selector 17, that is, on the byte data BD′3 made up of the data blocks DB12 and DB13 and arithmetic operation result blocks CRC320 and CRC321 in the example, by using output data D6 from the latch 16, that is, the arithmetic operation result CR12 in the example and produces an arithmetic operation result CR13. Then, the latch 16 latches the arithmetic operation result CR13 for a period of time being equivalent to one clock and, as shown in FIG. 24(5), outputs it as the output data D6 during a sixth period #6.
Then, the arithmetic operation section 20, during the sixth period #6, performs the CRC16 operation on the output data D3 from the selector 17, that is, on the byte data BD4 made up of arithmetic operation result blocks CRC322 and CRC323 in the example, by using output data D6 from the latch 16, that is, the arithmetic operation result CR13 and produces an arithmetic operation result CR14. Then, the latch 16 latches the arithmetic operation result CR14 for a period of time being equivalent to one clock and, as shown in FIG. 24(5), outputs it as the output data D6 during a seventh period #7. This arithmetic operation result CR14 becomes the arithmetic operation result CRC16. The arithmetic operation result CRC16, as described above, is made up of two pieces of the arithmetic operation results CRC160 and CRC161.
Then, the selector 18, during the third period #3 to fifth period #5, selects the output data D2 output from the latch 13, that is, any one of the byte data BD0 to BD2 in the example and outputs it as output data D7. Moreover, the selector 18, during the sixth period #6, outputs the byte data BD′3 made up of data blocks DB12 and DB13 and the arithmetic operation result blocks CRC320 and CRC321 as the output data D7. Furthermore, the selector 18, during the seventh period #7, produces new byte data BD′4 using the arithmetic operation result blocks CRC322 and CRC323 making up the arithmetic operation result CRC32 and arithmetic operation result blocks CRC160 and CRC161 making up the arithmetic operation result CRC16 and outputs it as the output data D7. Therefore, the data outputting section 21, as shown in FIG. 24(6), performs waveform shaping on the output data D7 being output by 32 bits from the selector 18 and feeds it as an output data D8 to circuit elements at a later stage.
Generally, in data communications, in order to transmit data accurately to a receiver, continuous transmission from a beginning to an end of the data transmission (in the case of a packet communication, during transmission of at least one packet) is required. To achieve this, in the conventional CRC arithmetic operation circuit described above, as shown in FIG. 24, an arithmetic operation result is added to an end of data to be transmitted so that both the data to be transmitted and the CRC arithmetic operation result are continuously transmitted without interruption.
In the conventional CRC arithmetic operation circuit, since the arithmetic operation result CRC32 obtained by the CRC operation is used to perform the CRC16 operation, it is necessary to add the arithmetic operation result CRC32 to an end of the output data D1 fed from the data inputting section 11 and then to feed it to the arithmetic operation section 20.
However, as shown in FIG. 24(1), if an end of the output data D1 being output by 32 bits from the data inputting section 11 is the byte data BD3 being of two bytes, following inconvenience occurs. That is, since the arithmetic operation result CRC32 is made up of four arithmetic operation result blocks CRC320 to CRC323 each being of one byte, as shown in FIG. 24(4), the arithmetic operation result blocks CRC321 and CRC322 being a first half of the arithmetic operation result CRC32 can be transmitted as the byte data DB′3 by adding these two blocks CRC321 and CRC322 to the data blocks BD12 and BD13 to the arithmetic operation section 20 during the fifth period #5. On the other hand, in order to transmit the remaining arithmetic operation result blocks CRC322 and CRC323 being a latter half of the arithmetic operation result CRC32, as shown in FIG. 24(4), new byte data BD4 has to be produced and to be then transmitted during the sixth period #6 to the arithmetic operation section 20. That is, at this point, since data transmission not associated directly with the CRC16 operation has to be carried out, additional time being equivalent to one clock is needed. Therefore, the latch 14, in order to adjust timing between the data transmission requiring the additional time being equivalent to one clock and the CRC16 operation in the arithmetic operation section 20, latches the output data D1 from the data inputting section 11 during the time being equivalent to one clock.
Moreover, to perform the CRC operation, time being equivalent to at least one clock is necessary and therefore the latches 15 and 16 are mounted at a latter stage of each of the arithmetic operation sections 19 and 20. As a result, a time delay being equivalent to two clocks occurs between inputting of the input data D0 to the data inputting section 11 and outputting of the output data D8 from the data outputting section 21. To solve this problem, in the conventional CRC arithmetic operation circuit, the latch 12 corresponding to the latch 14 is mounted and the latch 13 corresponding to the latches 15 and 16 is mounted between the data inputting section 11 and the selector 18.
Because of this, the conventional CRC arithmetic operation circuit has a problem in that it cannot meet requirements for high-speed signal processing in data communications induced by high-speed operations of CPUs (Central Processing Unit) in recent years. This inconvenience also occurs even in the case of data communications in which data is transmitted by performing the CRC operation a plurality of numbers of times. It is impossible to meet the requirement for high-speed signal processing in data communications only by increasing a data transmission speed and/or increasing a width of a bus and, therefore, an increase in the processing speed within a signal processing circuit is essential.